package leetcode;
/*
 * 打家劫舍
 * */
public class Day15 {
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0]+rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }

    private int rob1(int[] nums, int left, int right) {
        if(left>right) return 0;
        int n=nums.length;
        int[] f=new int[n];
        int[] g=new int[n];
        f[left]=nums[left];
        for (int i=left+1;i<=right;i++){
            f[i]=g[i-1]+nums[i];
            g[i]=Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[right],g[right]);
    }


}
